package com.isaiah.graph.adjacencylist;

/**
 * @Title: 图的深度搜索
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/613:30
 */
public class DepthFirstSearch {
    /** 索引代表顶点， 值表示当前顶点是否已被访问过 */
    private boolean[] isVisited;
    /** 记录有多少个顶点与s顶点相通 */
    private int count;

    public DepthFirstSearch(Graph G, int s) {
        // 初始化isVisited数组
        this.isVisited = new boolean[G.V()];
        // 初始化跟顶点s相通的顶点数量
        this.count = 0;
        // 深度遍历
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        // 把v顶点标记为已搜索
        isVisited[v] = true;
        for (Integer w: G.addj(v)){
            // 判断顶点w有没有被访问过，如果没有，则递归调用dfs方法进行深度搜索
            if (!isVisited[w]){
                dfs(G, w);
            }
        }
        // 相通顶点数量加1
        count++;
    }

    /**
     * 判断顶点w与s顶点是否相通
     * @param w
     * @return
     */
    public boolean isVisited(int w){
        return isVisited[w];
    }

    /**
     * 获取与s顶点相通所有顶点的总数
     * @return
     */
    public int count(){
        return count;
    }
}
